<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
    <style>
        #el_1,
        #el_2 {
            display: flex;
        }

        #el_1>div,
        #el_2>div {
            margin: 10px 20px;

        }

        .txtSelect {
            text-decoration: underline;
            color: red;
            font-weight: bold;
        }

        .txtSuccess {
            color: green;
            text-decoration: line-through;
            font-weight: bold;
        }

        .txtDelete {
            text-decoration: line-through;
            color: #909090;
            font-weight: bold;
        }

        .txtAdd {
            text-decoration: underline;
            color: yellow;
            font-weight: bold;
        }
    </style>
</head>

<body>

    <div id="el_1"></div>
    <div id="el_2"></div>
    <div>
        比较过程:
        <h1 id="bj_1"></h1>
        <h1 id="bj_2"></h1>
        <h1 id="bj_3"></h1>
    </div>
    <div>
        比较结果:
    </div>
    <div id="container"></div>
</body>



<script>
    let arr = []
    let container = document.getElementById("container")
    let el_1 = document.getElementById("el_1")
    let el_2 = document.getElementById("el_2")

    let bj_1 = document.getElementById("bj_1")
    let bj_2 = document.getElementById("bj_2")
    let bj_3 = document.getElementById("bj_3")


    let oldArr = randomilize([1, 2, 3, 4, 5, 6,7])
    let old_node = oldArr.map((item) => {
        return {
            key: item
        }
    })
    let newArr = randomilize([1, 2, 3, 4, 5])
    let new_node = newArr.map((item) => {
        return {
            key: item
        }
    })
    console.log('旧数组:', oldArr.join(','))
    console.log('新数组:', newArr.join(','))

    //挂载Dom
    patchDom(old_node, container)

    patchDomArr(oldArr, el_1, 'o')
    patchDomArr(newArr, el_2, 'n')


    function clear(attr) {
        for (let index = 0; index < el_1.children.length; index++) {
            const element = el_1.children[index];
            if (element.className.trim() === attr) {
                element.className = ''
            }
        }
        for (let index = 0; index < el_2.children.length; index++) {
            const element = el_2.children[index];
            if (element.className.trim() === attr) {
                element.className = ''
            }
        }
    }


    function diff(prevChildren, nextChildren) {
        let oldStartIdx = 0
        let oldEndIdx = prevChildren.length - 1
        let newStartIdx = 0
        let newEndIdx = nextChildren.length - 1

        let oldStartVNode = prevChildren[oldStartIdx]
        let oldEndVNode = prevChildren[oldEndIdx]
        let newStartVNode = nextChildren[newStartIdx]
        let newEndVNode = nextChildren[newEndIdx]

        while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {

            if (!oldStartVNode) {  //undefined时前移一位
                oldStartVNode = prevChildren[++oldStartIdx]
            } else if (!oldEndVNode) {  //undefined时后移一位
                oldEndVNode = prevChildren[--oldEndIdx]
            } else if (diffConditions(oldStartVNode.key, newStartVNode.key) && oldStartVNode.key === newStartVNode.key) {  //1.开始与开始
                //真实DOM引用
                newStartVNode.el = oldStartVNode.el

                oldStartVNode = prevChildren[++oldStartIdx]
                newStartVNode = nextChildren[++newStartIdx]
            } else if (diffConditions(oldEndVNode.key, newEndVNode.key) && oldEndVNode.key === newEndVNode.key) {      //2.结束与结束    
                //真实DOM引用
                newEndVNode.el = oldEndVNode.el

                oldEndVNode = prevChildren[--oldEndIdx]
                newEndVNode = nextChildren[--newEndIdx]
            } else if (diffConditions(oldStartVNode.key, newEndVNode.key) && oldStartVNode.key === newEndVNode.key) { //3.开始与结束
                //真实DOM引用
                newEndVNode.el = oldStartVNode.el

                container.appendChild(
                    oldStartVNode.el
                )
                // 更新索引，指向下一个位置
                oldStartVNode = prevChildren[++oldStartIdx]
                newEndVNode = nextChildren[--newEndIdx]
            } else if (diffConditions(oldEndVNode.key, newStartVNode.key) && oldEndVNode.key === newStartVNode.key) { //4.结束与开始   
                //真实DOM引用
                newStartVNode.el = oldEndVNode.el

                container.insertBefore(oldEndVNode.el, oldStartVNode.el)
                oldEndVNode = prevChildren[--oldEndIdx]
                newStartVNode = nextChildren[++newStartIdx]
            } else {
                 
                const idxInOld = prevChildren.findIndex((node,index) => {
                    if (node && index >= oldStartIdx) {
                        diffConditions(node.key, newStartVNode.key)
                    }
                    if (node && node.key === newStartVNode.key) {
                        return true
                    }
                })
                if (idxInOld >= 0) {
                    const vnodeToMove = prevChildren[idxInOld]
                    //真实DOM引用
                    newStartVNode.el = vnodeToMove.el
                    container.insertBefore(vnodeToMove.el, oldStartVNode.el)
                    prevChildren[idxInOld] = undefined
                } else {
                    diffConditions(null, newStartVNode.key, true)
                    let div = document.createElement('div')
                    div.innerText = newStartVNode.key
                    newStartVNode.el = div
                    container.insertBefore(div, oldStartVNode.el)
                }
                //新数组移动一位，旧数组是否移动就看如果是首位undefined,++
                //末尾undefined , --在上面的逻辑中
                newStartVNode = nextChildren[++newStartIdx]
            }
        }
        //如果两个数组只是顺序换位，那么最终的索引结果都是开始比结束大1
        console.log('最终索引：', oldStartIdx, oldEndIdx, ':', newStartIdx, newEndIdx);

        if (oldStartIdx > oldEndIdx) { //如果旧数组少了，那么走此路线         
            let refElm = nextChildren[newEndIdx + 1]

            //剩余的新数组内容全部插入进去
            for (; newStartIdx <= newEndIdx; ++newStartIdx) {
                let vnode = nextChildren[newStartIdx]
                let div = document.createElement('div')
                div.innerText = vnode.key
                vnode.el = div
                if (refElm !== undefined) {
                    container.insertBefore(vnode.el, refElm.el)
                } else {
                    container.appendChild(vnode.el)
                }
                diffConditions(null, vnode.key, true)
            }
        } else if (newStartIdx > newEndIdx) { //如果新数组少了，那么走此路线
            for (let i = oldStartIdx; i <= oldEndIdx; i++) {
                //多余的旧数组内容，删除
                prevChildren[i] && container.removeChild(prevChildren[i].el)
                prevChildren[i] && diffConditions(prevChildren[i].key, null, false, true)
            }
        }

        console.log('最终索引：', oldStartIdx, oldEndIdx, ':', newStartIdx, newEndIdx);

    }


    function patchDom(nodeArr, el) {
        for (const item of nodeArr) {
            let div = document.createElement('div')
            div.innerText = item.key || item
            item.el = div
            el.appendChild(item.el)
        }
    }
    function patchDomArr(arr, el, pre) {
        for (const item of arr) {
            let div = document.createElement('div')
            div.innerText = item
            div.setAttribute('id', pre + item)
            el.appendChild(div)
        }
    }
    
    function diffConditions(oneKey = '', twoKey = '', isNew = false, isDel = false) {
        let item = {
            oneKey,
            twoKey
        }
        if (isNew) {
            item.isNew = true
        }
        if (isDel) {
            item.isDel = true
        }
        arr.push(item)
        return true
    }



    //将数组打乱顺序
    function randomilize(arr) {
        var length = arr.length;
        var arr1 = new Array();
        for (var i = 0; i < length; i++) {
            arr1[i] = i;
        }   //建立数组下标数组
        var arr2 = new Array();
        for (var i = 0; i < length; i++) {
            arr2[i] = arr1.splice(Math.floor(Math.random() * arr1.length), 1);
        }  //将数组下标随机打乱
        var arr3 = new Array();
        for (var i = 0; i < length; i++) {
            arr3[i] = arr[arr2[i]];
        }  //将数组按打乱后的下标输出
        return arr3;
    }









    diff(old_node, new_node)

    console.log('真实旧数组:', old_node)
    console.log('真实新数组:', new_node)


    console.log(arr);

    let idx = 0
    let timer = setInterval(() => {

        clear('txtSelect')

        let item = arr[idx++]
        bj_1.innerText = item ? item.oneKey : ''
        bj_2.innerText = item ? item.twoKey : ''

        let oldOne = document.getElementById('o' + item.oneKey) || ''
        let oldTwo = document.getElementById('n' + item.twoKey) || ''

        if (item.oneKey === item.twoKey) {
            oldOne.className = 'txtSuccess'
            oldTwo.className = 'txtSuccess'
            bj_3.innerText = '相等'
        } else if (item.isNew) {
            oldTwo.className = 'txtAdd'
            oldOne.className = 'txtAdd'
            bj_3.innerText = '新增元素'
        } else if (item.isDel) {
            oldTwo.className = 'txtDelete'
            oldOne.className = 'txtDelete'
            bj_3.innerText = '删除元素'
        } else {
            oldOne.className = 'txtSelect'
            oldTwo.className = 'txtSelect'
            bj_3.innerText = '不相等'
        }


        if (arr.length === idx) {
            clearInterval(timer)
        }
    }, 500)

</script>


</html>